/**
 * A和B是两个带头结点的单链表，其中元素递增有序。
 * 设计一个算法从A和B中的公共元素产生单链表C，要求不破坏A和B链表
 * 该算法的时间复杂度:T(n)=O(len(A)+len(B)), 空间复杂度为O(1)
 */

#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	struct LNode* next;
	int data;
} LNode, *LinkedList;

bool init(LinkedList &list);

bool insert(LinkedList &list, int data);

void print(LinkedList &list);

bool core(LinkedList &A, LinkedList &B);

int main()
{
	LinkedList A=NULL;
	LinkedList B=NULL;
	init(A);
	init(B);
	
	insert(A,1);
	insert(A,2);
	insert(A,4);
	insert(A,6);
	insert(A,7);
	insert(A,8);
	
	insert(B,0);
	insert(B,2);
	insert(B,3);
	insert(B,5);
	insert(B,7);
	insert(B,8);
	
	core(A,B);
	return 0;
}

bool init(LinkedList &list)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	list=newNode;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	while(node->next) node=node->next;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

bool core(LinkedList &A, LinkedList &B)
{
	LNode* pa=A->next;		//pa为A链表的遍历结点
	LNode* pb=B->next;		//pb为B链表的遍历结点
	
	LNode* publicNode=NULL;
	LinkedList C=(LNode* )malloc(sizeof(LNode));	//用于存放公共结点的链表
	if(!C) return false;
	C->next=NULL;
	LNode* pc=C;			//pc指向C链表的最后一个元素，方便进行尾插操作
	
	while(pa && pb)
	{
		if(pa->data < pb->data)
		{
			pa=pa->next;
		} else if(pa->data > pb->data){
			pb=pb->next;
		} else{
			//pa->data==pb->data
			publicNode=(LNode* )malloc(sizeof(LNode));
			if(!publicNode) return false;
			publicNode->data=pa->data;
			publicNode->next=NULL;
			pc->next=publicNode;		//尾插法插入公共元素
			pc=publicNode;				//修改pc指针指向，指向链表C的最后一个元素
			pa=pa->next;
			pb=pb->next;
		}
		pc->next=NULL;	//置C的尾结点的后继为空
	}
	print(A);
	print(B);
	print(C);
	return true;
}
